package comUtils;

/**@description
 * 二叉查找树(排序树)基本类
 * @author Jintao_Ma
 */
public class BSTree<T extends Comparable<T>>{
	/*基本方法*/
	private boolean isNull(BSNode<T> bSNode){
		return null == bSNode;
	}
	
	private boolean isNotNull(BSNode<T> bSNode){
		return !isNull(bSNode);
	}
	
	BSNode<T> root; /*根节点*/
	
	public class BSNode<S extends Comparable<T>>{
		S key; /*当前节点的值*/
		BSNode<S> parent; /*父节点,设置该属性是为了更方便的查找上级*/
		BSNode<S> left; /*左孩子*/
		BSNode<S> right; /*右孩子*/
		
		public BSNode(S key, BSNode<S> parent, BSNode<S> left, BSNode<S> right) {
			super();
			this.key = key;
			this.parent = parent;
			this.left = left;
			this.right = right;
		}
	}

	/**@description 
	 * 初始化二叉树
	 */
	public BSTree(){
	}
	
	/**@description
	 * 判断树是否为空
	 */
	public boolean isEmpty(){
		return isNull(root);
	}
	
	/**@description
	 * 初始化二叉树
	 */
	public void init(){
		root = null;
	}
	
	/**@description
	 * 判断节点是不是根节点
	 */
	public boolean isRoot(BSNode<T> bSNode){
		return (root == bSNode)? true:false;
	}
	
	/**@description 
	 * 添加节点
	 */
	public boolean addBSNode(T key){
		/*判断添加节点是否成功*/
		boolean result = true;
		BSNode<T> bSNode = new BSNode<T>(key, null, null, null);
		if(isEmpty()){
			root = bSNode;
		}else{
			result =  insert(root,bSNode);
		}
		return result;
	}
	private boolean insert(BSNode<T> root,BSNode<T> bSNode){
		/*判断添加节点是否成功*/
		boolean result = true;
		if(bSNode.key.compareTo(root.key) < 0){
			if(isNotNull(root.left)){
				result = insert(root.left,bSNode);
			}else{
				root.left = bSNode;
				bSNode.parent = root;
			}
		}else if(bSNode.key.compareTo(root.key) > 0){
			if(isNotNull(root.right)){
				result = insert(root.right,bSNode);
			}else{
				root.right = bSNode;
				bSNode.parent = root;
			}
		}else{
			result = false;/*值相等什么也不做*/
		}
		return result;
	}
	
	
	/**@description 
	 * 删除节点,如果不破坏树的结构(中序遍历是递增的)，那么分三种情况：
	 * 1)需要删除的节点下并没有其他子节点
	 * 2)需要删除的节点下有一个子节点(左或者右)
	 * 3)需要删除的节点下有两个子节点(通过查找它的前驱节点(后继节点)，然后替换该节点，最后删除前驱节点(后继节点))
	 */
	public boolean delBSNode(T key){
		boolean del = false;
		BSNode<T> BSNode = findAllNode(key);
		if(isNull(BSNode)){
			return del;
		}else{
		}
		/**该节点无任何子节点*/
		if(isNull(BSNode.left) && isNull(BSNode.right)){
			if(!isRoot(BSNode)){  /*非根节点*/
				if(BSNode==BSNode.parent.left){ /*如果是父节点的左孩子*/
					BSNode.parent.left = null;  /*删除父节点的左引用*/
				}else{
					BSNode.parent.right = null; /*删除父节点的右引用*/
				}
			}else{ /*根节点*/
				init();
			}
			del = true;
		/**该节点只有一个子节点*/
		}else if(isNull(BSNode.left) || isNull(BSNode.right)){
			if(!isRoot(BSNode)){ /*非根节点*/
				if(isNull(BSNode.left)){ /*该节点只有一个右孩子*/
					if(BSNode==BSNode.parent.left){ /*如果是父节点的左孩子*/
						BSNode.parent.left = BSNode.right; /*父节点的左引用指向该节点的右孩子*/
					}else{
						BSNode.parent.right = BSNode.right; /*父节点的右引用指向该节点的右孩子*/
					}
					BSNode.right.parent = BSNode.parent; /*修改右孩子的父引用*/ 
				}else{ /*该节点只有一个左孩子*/
					if(BSNode==BSNode.parent.left){ /*如果是父节点的左孩子*/
						BSNode.parent.left = BSNode.left; /*父节点的左引用指向该节点的左孩子*/
					}else{
						BSNode.parent.right = BSNode.left; /*父节点的右引用指向该节点的左孩子*/
					}
					BSNode.left.parent = BSNode.parent; /*修改左孩子的父引用*/ 
				}
			}else{ /*根节点*/
				if(isNull(BSNode.left)){
					BSNode.right.parent = null;
					root = BSNode.right;
				}else{
					BSNode.left.parent = null;
					root = BSNode.left;
				}
			}
			del = true;
		/**两个子节点*/
		}else{
			BSNode<T> preNode = MaxBode(BSNode.left);/*先查找该节点的前驱节点(后继节点)*/
			SwitchKey(preNode,BSNode);/*交换两个BSNode的值*/
			del = delBSNode(preNode.key);
		}
		return del;
	}
	
	/**@description
	 * 交换两个Node的值
	 */
	public void SwitchKey(BSNode<T> A,BSNode<T> B){
		T key;
		key = A.key;
		A.key = B.key;
		B.key = key;
	}
	
	/**@description
	 * 返回key所在的节点(中序查找所有节点)
	 */
	public BSNode<T> findAllNode(T key){
		return isNull(root)? null:middleFindByKey(root,key);
	}
	
	/**@description
	 * 使用递归的方法删除节点
	 * @param 
	 * tree 要删除节点的子树
	 * key 要删除的对应key值的节点
	 * @return
	 * 返回删除后子树
	 * 如果
	 * 1.没有值对应的节点
	 * 2.要删除的节点没有左右孩子
	 * 3.要删除的节点只有左孩子或者右孩子
	 * 那么返回null
	 */
	public BSNode<T> delNode(BSNode<T> tree, T key){
		/*该节点存在*/
		if(isNotNull(tree)){
			if(key.compareTo(tree.key) < 0){
				tree.left = delNode(tree.left,key);
				if(isNotNull(tree.left)){
					tree.left.parent = tree;
				}else{
				}
			}else if(key.compareTo(tree.key) > 0 ){
				tree.right = delNode(tree.right,key);
				if(isNotNull(tree.right)){
					tree.right.parent = tree;
				}else{
				}
			}else{ /*key值与当前树的根节点的值相等*/
				if(isNotNull(tree.left) && isNotNull(tree.right)){
					BSNode<T> switchNode = MinBode(tree.right);
					SwitchKey(switchNode,tree);
					tree.right = delNode(tree.right,key);
				}else{
					tree = isNotNull(tree.left)? tree.left:tree.right;
				}
			}
		}
		return tree;
	}
	
	public void delNode(T key){
		delNode(root, key);
	}
	
	public BSNode<T> middleFindByKey(BSNode<T> treeNode,T key){
		BSNode<T> bSNode = null;
		/*优先查找左自树*/
		if(isNotNull(treeNode.left)){
			bSNode = middleFindByKey(treeNode.left,key);
			if(isNotNull(bSNode)){
				return bSNode;
			}
		}else{
		}
		/*查找中间节点*/
		if(0 == treeNode.key.compareTo(key)){
			return bSNode = treeNode;
		}else{
		}
		/*查找右子树*/
		if(isNotNull(treeNode.right)){
			bSNode = middleFindByKey(treeNode.right,key);
			if(isNotNull(bSNode)){
				return bSNode;
			} 
		}else{
		}
		return bSNode;
	}
	
	public BSNode<T> middleFindByKey(T key){
		return middleFindByKey(root,key);
	}
	
	/**@description
	 * 查找树(子树)中的最大节点  即后继节点
	 * @return
	 * BSNode<T>
	 */
	public BSNode<T> MaxBode(BSNode<T> tree){
		if(isNotNull(tree)){
			if(isNotNull(tree.right)){
				return MaxBode(tree.right);
			}else{
				return tree;
			}
		}else{
			return null;
		}
	}
	
	/**@description
	 * 查找树(子树)中的最小节点  即前驱节点
	 * @return
	 * BSNode<T>
	 */
	public BSNode<T> MinBode(BSNode<T> tree){
		if(isNotNull(tree)){
			if(isNotNull(tree.left)){
				return MinBode(tree.left);
			}else{
				return tree;
			}
		}else{
			return null;
		}
	}
	
	/**@description 
	 * 前序遍历
	 */
	public void beforeFind(BSNode<T> treeNode){
		if(isNotNull(treeNode)){
			System.out.println(treeNode.key);
			beforeFind(treeNode.left);
			beforeFind(treeNode.right);
		}else{
		}
	}
	public void beforeFind(){
		beforeFind(root);
	}
	
	/**@description 
	 * 中序遍历
	 */
	public void middleFind(BSNode<T> treeNode){
		if(isNotNull(treeNode)){
			middleFind(treeNode.left);
			System.out.println(treeNode.key);
			middleFind(treeNode.right);
		}else{
		}
	}
	public void middleFind(){
		middleFind(root);
	}
	
	/**@description 
	 * 后序遍历
	 */
	public void afterFind(BSNode<T> treeNode){
		if(isNotNull(treeNode)){
			afterFind(treeNode.left);
			afterFind(treeNode.right);
			System.out.println(treeNode.key);
		}else{
		}
	}
	public void afterFind(){
		afterFind(root);
	}
	
	/*测试函数*/
	public static void main(String[] args) {
		BSTree<Integer> bSTree = new BSTree<Integer>();
		bSTree.addBSNode(new Integer(2));
		bSTree.addBSNode(new Integer(1));
		bSTree.addBSNode(new Integer(4));
		bSTree.addBSNode(new Integer(3));
		bSTree.addBSNode(new Integer(5));
		bSTree.addBSNode(new Integer(6));
		bSTree.addBSNode(new Integer(9));
		bSTree.addBSNode(new Integer(7));
		bSTree.addBSNode(new Integer(8));
		
//		bSTree.delNode(new Integer(1));
//		bSTree.delNode(new Integer(2));
//		bSTree.delNode(new Integer(3));
//		bSTree.delNode(new Integer(4));
//		bSTree.delNode(new Integer(5));
//		bSTree.delNode(new Integer(6));
//		bSTree.delNode(new Integer(7));
//		bSTree.delNode(new Integer(8));
//		bSTree.delNode(new Integer(9));
		
//		bSTree.beforeFind();/*先序遍历*/
		bSTree.middleFind();/*中序遍历*/ 
//		bSTree.afterFind();/*后序遍历*/
	}
}
